package offer;

import java.util.*;

/**
 * @Author Elephas
 * @Date 2022/1/30
 **/
@FunctionalInterface
public interface MajorityElement2 {
    /**
     * Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
     * @param nums
     * @return
     */
    List<Integer> majorityElement(int[] nums);
}

class MajorityElement2Impl1 implements MajorityElement2{
    /**
     * time : o(nlogn), space o(logn)
     * Sort the array, then count elements that appear more than ⌊ n/3 ⌋ times.
     * @param nums
     * @return
     */
    @Override
    public List<Integer> majorityElement(int[] nums) {
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] != nums[i-1]){
                int frequency = end - start + 1;
                if(frequency > nums.length / 3){
                    ans.add(nums[start]);
                }
                start = i;
                end = i;
            }else{
                end++;
            }
        }
        int frequency = end - start + 1;
        if(frequency > nums.length / 3){
            ans.add(nums[start]);
        }
        return ans;
    }
}


class MajorityElement2Impl2 implements MajorityElement2{
    /**
     * time: o(n), space: o(n)
     * using a hash map.
     * @param nums
     * @return
     */
    @Override
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            insert(map,num);
        }
        List<Integer> ans = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet() ){
            int freq = entry.getValue();
            int element = entry.getKey();
            if(freq > nums.length / 3){
                ans.add(element);
            }
        }
        return ans;
    }
    private void insert(Map<Integer,Integer> map, int element){
        int freq = map.getOrDefault(element,0);
        map.put(element,freq+1);
    }
}

class MajorityElement2Impl3 implements MajorityElement2{
    /**
     * 摩尔投票法
     * 主元素至多两个，选两个 candidate
     * @param nums
     * @return
     */
    @Override
    public List<Integer> majorityElement(int[] nums) {
        return null;

    }
}